{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Last Stone Weight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lastStoneWeight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最后一块石头的重量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一堆石头，每块石头的重量都是正整数。</p>\n",
    "\n",
    "<p>每一回合，从中选出两块<strong> 最重的</strong> 石头，然后将它们一起粉碎。假设石头的重量分别为 <code>x</code> 和 <code>y</code>，且 <code>x <= y</code>。那么粉碎的可能结果如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>x == y</code>，那么两块石头都会被完全粉碎；</li>\n",
    "\t<li>如果 <code>x != y</code>，那么重量为 <code>x</code> 的石头将会完全粉碎，而重量为 <code>y</code> 的石头新重量为 <code>y-x</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 <code>0</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[2,7,4,1,8,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，\n",
    "再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，\n",
    "接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，\n",
    "最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= stones.length <= 30</code></li>\n",
    "\t<li><code>1 <= stones[i] <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [last-stone-weight](https://leetcode.cn/problems/last-stone-weight/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [last-stone-weight](https://leetcode.cn/problems/last-stone-weight/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,7,4,1,8,1]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 初始化\n",
    "        heap = [-stone for stone in stones]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        # 模拟\n",
    "        while len(heap) > 1:\n",
    "            x,y = heapq.heappop(heap),heapq.heappop(heap)\n",
    "            if x != y:\n",
    "                heapq.heappush(heap,x-y)\n",
    "\n",
    "        if heap: return -heap[0]\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: list[int]) -> int:\n",
    "        for index, i in enumerate(stones):\n",
    "            stones[index] = -stones[index]\n",
    "        while len(stones) > 1:\n",
    "            heapq.heapify(stones)\n",
    "            a = -heapq.heappop(stones)\n",
    "            b = -heapq.heappop(stones)\n",
    "            if a != b:\n",
    "                a = abs(a - b)\n",
    "                heapq.heappush(stones, -a)\n",
    "            elif a == b:\n",
    "                continue\n",
    "        if len(stones) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return -stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        max_heap = [-stone for stone in stones]  # 转换为最大堆，存储负数\n",
    "        heapq.heapify(max_heap)\n",
    "        \n",
    "        while len(max_heap) >= 2:\n",
    "            y = -heapq.heappop(max_heap)\n",
    "            x = -heapq.heappop(max_heap)\n",
    "            \n",
    "            if x != y:\n",
    "                heapq.heappush(max_heap, -(y - x))\n",
    "        \n",
    "        return 0 if not max_heap else -max_heap[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        q = []\n",
    "        heapq.heapify(q)\n",
    "        for i in stones:\n",
    "            heapq.heappush(q, -i)\n",
    "        \n",
    "        while len(q) > 1:\n",
    "            stoneY = -heapq.heappop(q)\n",
    "            stoneX = -heapq.heappop(q)\n",
    "            if stoneY != stoneX:\n",
    "                stoneY -= stoneX\n",
    "                heapq.heappush(q, -stoneY)\n",
    "        \n",
    "        if q:\n",
    "            return -q[0]\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 初始化\n",
    "        heap = [-stone for stone in stones]\n",
    "        heapq.heapify(heap)\n",
    "        # 模拟\n",
    "        while len(heap) > 1:\n",
    "            x, y = heapq.heappop(heap),heapq.heappop(heap)\n",
    "            if x != y:\n",
    "                heapq.heappush(heap,x-y)\n",
    "\n",
    "        if heap: return -heap[0]\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        heap = [-i for i in stones]\n",
    "        heapq.heapify(heap)\n",
    "        while heap:\n",
    "            stone1 = heapq.heappop(heap) * -1\n",
    "            if not heap:\n",
    "                return stone1\n",
    "            else:\n",
    "                stone2 = heapq.heappop(heap) * -1\n",
    "                stone1 = stone1 - stone2\n",
    "                heapq.heappush(heap, stone1 * -1)\n",
    "        return 0\n",
    "        \n",
    "class Heap:\n",
    "    def __init__(self,desc=False):\n",
    "        \"\"\"\n",
    "        初始化，默认创建一个小顶堆\n",
    "        \"\"\"\n",
    "        self.heap = []\n",
    "        self.desc = desc\n",
    "    \n",
    "    @property\n",
    "    def size(self):\n",
    "        return len(self.heap)\n",
    "    \n",
    "    def top(self):\n",
    "        if self.size:\n",
    "            return self.heap[0]\n",
    "        return None\n",
    "    \n",
    "    def push(self,item):\n",
    "        \"\"\"\n",
    "        添加元素\n",
    "        第一步，把元素加入到数组末尾\n",
    "        第二步，把末尾元素向上调整\n",
    "        \"\"\"\n",
    "        self.heap.append(item)\n",
    "        self._sift_up(self.size-1)\n",
    "    \n",
    "    def pop(self):\n",
    "        \"\"\"\n",
    "        弹出堆顶\n",
    "        第一步，记录堆顶元素的值\n",
    "        第二步，交换堆顶元素与末尾元素\n",
    "        第三步，删除数组末尾元素\n",
    "        第四步，新的堆顶元素向下调整\n",
    "        第五步，返回答案\n",
    "        \"\"\"\n",
    "        item = self.heap[0]\n",
    "        self._swap(0,self.size-1)\n",
    "        self.heap.pop()\n",
    "        self._sift_down(0)\n",
    "        return item\n",
    "    \n",
    "    def _smaller(self,lhs,rhs):\n",
    "        return lhs > rhs if self.desc else lhs < rhs\n",
    "    \n",
    "    def _sift_up(self,index):\n",
    "        \"\"\"\n",
    "        向上调整\n",
    "        如果父节点和当前节点满足交换的关系\n",
    "        （对于小顶堆是父节点元素更大，对于大顶堆是父节点更小），\n",
    "        则持续将当前节点向上调整\n",
    "        \"\"\"\n",
    "        while index:\n",
    "            parent = (index-1) // 2\n",
    "            \n",
    "            if self._smaller(self.heap[parent],self.heap[index]):\n",
    "                break\n",
    "                \n",
    "            self._swap(parent,index)\n",
    "            index = parent\n",
    "    \n",
    "    def _sift_down(self,index):\n",
    "        \"\"\"\n",
    "        向下调整\n",
    "        如果子节点和当前节点满足交换的关系\n",
    "        （对于小顶堆是子节点元素更小，对于大顶堆是子节点更大），\n",
    "        则持续将当前节点向下调整\n",
    "        \"\"\"\n",
    "        # 若存在子节点\n",
    "        while index*2+1 < self.size:\n",
    "            smallest = index\n",
    "            left = index*2+1\n",
    "            right = index*2+2\n",
    "            \n",
    "            if self._smaller(self.heap[left],self.heap[smallest]):\n",
    "                smallest = left\n",
    "                \n",
    "            if right < self.size and self._smaller(self.heap[right],self.heap[smallest]):\n",
    "                smallest = right\n",
    "                \n",
    "            if smallest == index:\n",
    "                break\n",
    "            \n",
    "            self._swap(index,smallest)\n",
    "            index = smallest\n",
    "    \n",
    "    def _swap(self,i,j):\n",
    "        self.heap[i],self.heap[j] = self.heap[j],self.heap[i]\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 初始化大顶堆\n",
    "        heap = Heap(desc=True)\n",
    "        for stone in stones:\n",
    "            heap.push(stone)\n",
    "\n",
    "        # 模拟\n",
    "        while heap.size > 1:\n",
    "            x,y = heap.pop(),heap.pop()\n",
    "            if x != y:\n",
    "                heap.push(x-y)\n",
    "        if heap.size: return heap.heap[0]\n",
    "        return 0\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 初始化\n",
    "        heap = [-stone for stone in stones]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        # 模拟\n",
    "        while len(heap) > 1:\n",
    "            x,y = heapq.heappop(heap),heapq.heappop(heap)\n",
    "            if x != y:\n",
    "                heapq.heappush(heap,x-y)\n",
    "\n",
    "        if heap: return -heap[0]\n",
    "        return 0\n",
    "\n",
    "class HeapImpl:\n",
    "    @staticmethod\n",
    "    def buildHeap(a: list, end):\n",
    "        for i in range(int(end / 2), 0, -1):\n",
    "            HeapImpl.heapify(a, i, end)\n",
    "\n",
    "    @staticmethod\n",
    "    def heapify(a: list, start, end):\n",
    "        if start >= end: return\n",
    "        i, p = start, start * 2\n",
    "        while True:\n",
    "            mp = i # maxPos\n",
    "            if p < end and a[p] > a[mp]:\n",
    "                mp = p\n",
    "            if p + 1 < end and a[p + 1] > a[mp]:\n",
    "                mp = p + 1\n",
    "\n",
    "            if mp == i:\n",
    "                break\n",
    "            a[mp], a[i] = a[i], a[mp]\n",
    "            i, p = mp, mp * 2\n",
    "\n",
    "\n",
    "class Heap:\n",
    "    def __init__(self, arr: list) -> None:\n",
    "        arr.append(arr[0])\n",
    "        arr[0], size = None, len(arr)\n",
    "        HeapImpl.buildHeap(arr, size)\n",
    "        self.a, self.size = arr, size\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size - 1\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.a[1:])\n",
    "\n",
    "    def top(self):\n",
    "        return self.a[1] if self.size > 1 else None\n",
    "\n",
    "    def pop(self):\n",
    "        if self.size < 2: return None\n",
    "        self.size -= 1\n",
    "        a, last = self.a, self.size\n",
    "\n",
    "        r = a[1]\n",
    "        a[1], a[last] = a[last], None\n",
    "        HeapImpl.heapify(a, 1, last)\n",
    "        return r\n",
    "\n",
    "    def push(self, val):\n",
    "        assert val is not None\n",
    "        a, i = self.a, self.size\n",
    "        self.a[i] = val\n",
    "        self.size += 1\n",
    "\n",
    "        p = int(i / 2)\n",
    "        while p >= 1 and a[i] > a[p]:\n",
    "            a[i], a[p] = a[p], a[i]\n",
    "            i, p = p, int(p / 2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        size = len(stones)\n",
    "        if size == 1: return stones[0]\n",
    "        if size == 2: return abs(stones[1] - stones[0])\n",
    "\n",
    "        hp = Heap(stones)\n",
    "\n",
    "        while len(hp) >= 2:\n",
    "            # take 2 stones\n",
    "            st1, st2 = hp.pop(), hp.pop()            \n",
    "            st = abs(st1 - st2)\n",
    "            if st > 0:\n",
    "                hp.push(st)\n",
    "\n",
    "        remain = hp.top()\n",
    "        return remain if remain else 0\n",
    "\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones = SortedList(stones)\n",
    "        while len(stones) >= 2:\n",
    "            x = stones.pop(-1)\n",
    "            y = stones.pop(-1)\n",
    "            if x > y:\n",
    "                stones.add(x-y)\n",
    "        return 0 if not stones else stones[0]\n",
    "\n",
    "# var lastStoneWeight = function(stones) {\n",
    "#     const pq = new MaxPriorityQueue();\n",
    "#     for (const stone of stones) {\n",
    "#         pq.enqueue('x', stone);\n",
    "#     }\n",
    "    \n",
    "#     while (pq.size() > 1) {\n",
    "#         const a = pq.dequeue()['priority'];\n",
    "#         const b = pq.dequeue()['priority'];\n",
    "#         if (a > b) {\n",
    "#             pq.enqueue('x', a - b);\n",
    "#         }\n",
    "#     }\n",
    "#     return pq.isEmpty() ? 0 : pq.dequeue()['priority'];\n",
    "# };\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            stones.sort(reverse = True)\n",
    "            y = stones[0]\n",
    "            x = stones[1]\n",
    "            if x == y:\n",
    "                stones = stones[2:]\n",
    "            else:\n",
    "                stones = stones[1:]\n",
    "                stones[0] = y - x\n",
    "        if len(stones) == 0:\n",
    "            return 0\n",
    "        return stones[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        q = []\n",
    "        for i in stones:\n",
    "            heappush(q,-i)\n",
    "        while len(q) >= 2:\n",
    "            a,b = -heappop(q),-heappop(q)\n",
    "            if a == b:continue\n",
    "            if a > b:\n",
    "                heappush(q,b-a)\n",
    "        return 0 if not len(q) else -q[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort()\n",
    "        \n",
    "        n = len(stones)\n",
    "        while n >= 2:\n",
    "            y = stones.pop()\n",
    "            x = stones.pop()\n",
    "            if x == y:\n",
    "                n -= 2\n",
    "            else:\n",
    "                stones.append(y - x)\n",
    "                stones.sort()\n",
    "                n -= 1\n",
    "        if n == 1:\n",
    "            return stones[-1]\n",
    "        elif n == 2:\n",
    "            if stones[0] == stones[1]:\n",
    "                return 0\n",
    "            else:\n",
    "                return abs(stones[0] - stones[1])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        h = [-stone for stone in stones]\n",
    "        heapq.heapify(h)\n",
    "\n",
    "        while len(h) > 1:\n",
    "            a, b = heapq.heappop(h), heapq.heappop(h)\n",
    "            if a != b:\n",
    "                heapq.heappush(h,a - b)\n",
    "        return -h[0] if h else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 使用Python 大根堆\n",
    "        # 特点：Python只有小根堆\n",
    "        heap = [-stone for stone in stones]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        while len(heap)>1:\n",
    "            x,y=heapq.heappop(heap),heapq.heappop(heap)\n",
    "            if x!=y:\n",
    "                heapq.heappush(heap,x-y)\n",
    "        return -heap[0] if heap else 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        while n>1:\n",
    "            stones.sort()\n",
    "            a = abs(stones.pop()-stones.pop())\n",
    "            if a>0:\n",
    "                stones.append(a)\n",
    "            n = len(stones)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        else:\n",
    "            return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort(reverse=True)\n",
    "\n",
    "        while len(stones) > 1:\n",
    "            a = stones.pop(0)\n",
    "            b = stones.pop(0)\n",
    "            if a>b:\n",
    "                stones.append(a-b)\n",
    "                stones.sort(reverse=True)\n",
    "        return stones[0] if stones else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones = [-s for s in stones]\n",
    "        heapq.heapify(stones)\n",
    "        while len(stones) >= 2:\n",
    "            x = heapq.heappop(stones)\n",
    "            y = heapq.heappop(stones)\n",
    "            if x != y:\n",
    "                heapq.heappush(stones, -abs(x - y))\n",
    "        return -heapq.heappop(stones) if stones else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) != 1 and len(stones) != 0:\n",
    "            stones.sort()\n",
    "            y = stones.pop()\n",
    "            x = stones.pop()\n",
    "            if x == y:\n",
    "                continue\n",
    "            else:\n",
    "                stones.append(y-x)\n",
    "        if len(stones) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones)>1:\n",
    "            stones.sort()\n",
    "            y=stones[-1]\n",
    "            x=stones[-2]\n",
    "            if x==y:\n",
    "                stones=stones[:-2]\n",
    "            else:\n",
    "                stones=stones[:-1]\n",
    "                stones[-1]=y-x\n",
    "        if len(stones)==1:\n",
    "            return stones[0]\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones)>=2:\n",
    "            stones.sort()\n",
    "            stones.append(stones.pop()-stones.pop())\n",
    "        return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            stones.sort(reverse=True)  # 从大到小排序\n",
    "            max1 = stones.pop(0)\n",
    "            max2 = stones.pop(0)\n",
    "            if max1 != max2:\n",
    "                stones.append(max1 - max2)\n",
    "        return stones[0] if len(stones) == 1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort()\n",
    "        while len(stones)>1:\n",
    "            x=stones.pop()\n",
    "            y=stones.pop()\n",
    "            if x!=y:\n",
    "                stones.append(abs(y-x))\n",
    "                stones.sort()\n",
    "        if len(stones)==1:\n",
    "            return stones[0]\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        sclone=[-x for x in stones]\n",
    "        heapq.heapify(sclone)\n",
    "        while len(sclone)>=2:\n",
    "            x=heapq.heappop(sclone)\n",
    "            y=heapq.heappop(sclone)\n",
    "            z=min(x,y)-max(x,y)\n",
    "            if z<0: heapq.heappush(sclone,z)\n",
    "        if len(sclone)==0: return 0\n",
    "        else: return -sclone[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        heap=[]\n",
    "        for x in stones:\n",
    "            hq.heappush(heap,-x)\n",
    "\n",
    "        while len(heap)>1:\n",
    "            x=hq.heappop(heap)*-1\n",
    "            y=hq.heappop(heap)*-1\n",
    "            z=x-y\n",
    "            if z!=0:\n",
    "                hq.heappush(heap,-z)\n",
    "        if len(heap)==1:\n",
    "            return -heap[0]\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort()\n",
    "        while len(stones) >= 2:\n",
    "            stones.sort()\n",
    "            if stones[-2] == stones[-1]:\n",
    "                stones = stones[:-2]\n",
    "            else:\n",
    "                stones = [abs(stones[-2] - stones[-1])] + stones[:-2]\n",
    "        return stones[0] if stones else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 初始化\n",
    "        heap = [-stone for stone in stones]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        # 模拟\n",
    "        while len(heap) > 1:\n",
    "            x,y = heapq.heappop(heap),heapq.heappop(heap)\n",
    "            heapq.heappush(heap,x-y)\n",
    "\n",
    "        return -heap[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        if (len(stones) == 1):\n",
    "            return stones[0]\n",
    "        stones = sorted(stones)  # NlogN\n",
    "        print(stones)\n",
    "        while (len(stones) > 1):  # N*N\n",
    "            x = stones[-1]\n",
    "            y = stones[-2]\n",
    "            tmp = x - y\n",
    "            stones.pop(-1)\n",
    "            stones.pop(-1)\n",
    "            flag = 0\n",
    "            for i in range(len(stones)):\n",
    "                if (tmp <= stones[i]):\n",
    "                    stones.insert(i, tmp)\n",
    "                    flag = 1\n",
    "                    break\n",
    "            if (flag == 0):\n",
    "                stones.append(tmp)\n",
    "        return stones[0]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones)>1:\n",
    "            stones.sort()\n",
    "            x=stones.pop()\n",
    "            y=stones.pop()\n",
    "            if abs(x-y)!=0:\n",
    "                stones.append(abs(x-y))\n",
    "        if len(stones)==0:\n",
    "            return 0\n",
    "        return stones[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones)>1:\n",
    "            stones.sort()\n",
    "            stones.append(stones.pop()-stones.pop())\n",
    "        return stones[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort(reverse = True)\n",
    "        while len(stones) > 1:\n",
    "            i = 0\n",
    "            j = 1\n",
    "            tmp = stones[i] - stones[j]\n",
    "            stones.append(tmp)\n",
    "            stones.remove(stones[i])\n",
    "            stones.remove(stones[i])\n",
    "            stones.sort(reverse = True)\n",
    "        return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones)>1:\n",
    "            x=max(stones)\n",
    "            stones.remove(x)\n",
    "            y=max(stones)\n",
    "            stones.remove(y)\n",
    "            if x-y!=0:\n",
    "                stones.append(x-y)\n",
    "        if len(stones)!=0:\n",
    "            return stones[0]\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "\n",
    "        while len(stones) >= 2:\n",
    "\n",
    "            stones.sort(reverse=True)\n",
    "\n",
    "            y = stones.pop(0)\n",
    "\n",
    "            x = stones.pop(0)\n",
    "\n",
    "            if y > x:\n",
    "\n",
    "                stones.append(y - x)\n",
    "\n",
    "        if not stones:\n",
    "\n",
    "            return 0\n",
    "\n",
    "        else:\n",
    "\n",
    "            return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        if len(stones) > 1:\n",
    "            max1 = max(stones)\n",
    "            stones.remove(max1)\n",
    "            max2 = max(stones)\n",
    "            stones.remove(max2)\n",
    "            if max1 > max2:\n",
    "                stones.append(max1 - max2)\n",
    "            return self.lastStoneWeight(stones)\n",
    "        elif len(stones) == 1:\n",
    "            return stones[0]\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 法一：不断排序(时间复杂度高，无意义！)\n",
    "        # while len(stones) > 1:\n",
    "        #     stones.sort(reverse=True)  # 从大到小排序\n",
    "        #     max1 = stones.pop(0)\n",
    "        #     max2 = stones.pop(0)\n",
    "        #     if max1 != max2:\n",
    "        #         stones.append(max1 - max2)\n",
    "        # return stones[0] if stones else 0\n",
    "\n",
    "        # 法二：heapq库的堆化操作，实现优先队列\n",
    "        stones = [-stone for stone in stones]\n",
    "        heapq.heapify(stones)\n",
    "        while len(stones) > 1:\n",
    "            max1 = heapq.heappop(stones)\n",
    "            max2 = heapq.heappop(stones)\n",
    "            if max1 != max2:\n",
    "                heapq.heappush(stones, max1-max2)\n",
    "        return -stones[0] if stones else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        '''\n",
    "        def max2(x):\n",
    "            m = 0\n",
    "            n = -1\n",
    "            for i in x:\n",
    "                if i>=m:\n",
    "                    n = m\n",
    "                    m = i\n",
    "                elif i>=n:\n",
    "                    n = i\n",
    "        \n",
    "            return n\n",
    "        '''\n",
    "        if len(stones) == 1:\n",
    "            return stones[0]\n",
    "        else:\n",
    "            while len(stones)>1:\n",
    "                stones.sort()\n",
    "                if stones[-1]-stones[-2]>0:\n",
    "                    stones.append(stones[-1]-stones[-2])\n",
    "                    del stones[-2]\n",
    "                    del stones[-2]\n",
    "                else:\n",
    "                    del stones[-1]\n",
    "                    del stones[-1]\n",
    "            if stones == []:\n",
    "                return 0\n",
    "            return stones[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            y = stones.pop(stones.index(max(stones)))\n",
    "            x = stones.pop(stones.index(max(stones)))\n",
    "            if x == y:\n",
    "                continue\n",
    "            stones.append(y - x)\n",
    "        if stones: return stones[0]\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        import heapq\n",
    "        #优先队列\n",
    "        minStones = [-s for s in stones]\n",
    "        heapq.heapify(minStones)\n",
    "        while len(minStones) > 1:\n",
    "            y = heapq.heappop(minStones)\n",
    "            x = heapq.heappop(minStones)\n",
    "            if x > y :\n",
    "                heapq.heappush(minStones, y-x)\n",
    "        return  - heapq.heappop(minStones) if minStones else 0 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        h = [x* -1 for x in stones]\n",
    "        heapq.heapify(h)\n",
    "\n",
    "        while len(h) > 1:\n",
    "            x0 = heapq.heappop(h) * -1\n",
    "            x1 = heapq.heappop(h) * -1\n",
    "            if x0 < x1:\n",
    "                heapq.heappush(h, (x1 - x0) * -1)\n",
    "            elif x0 > x1:\n",
    "                heapq.heappush(h, (-x1 + x0) * -1)\n",
    "        if h == []:\n",
    "            return 0\n",
    "        else:\n",
    "            return h[0] * -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        h = list()\n",
    "        for s in stones:\n",
    "            heappush(h, -s)\n",
    "        \n",
    "        while len(h) > 1:\n",
    "            x = -heappop(h)\n",
    "            y = -heappop(h)\n",
    "            if x > y:\n",
    "                heappush(h, y-x)\n",
    "        \n",
    "        if not h:\n",
    "            return 0\n",
    "        return -heappop(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        heap = []\n",
    "        for stone in stones:\n",
    "            heappush(heap, -stone)\n",
    "        while len(heap) > 1:\n",
    "            heaviest = -heappop(heap)\n",
    "            secondHeaviest = -heappop(heap)\n",
    "            if heaviest > secondHeaviest:\n",
    "                heappush(heap, -(heaviest - secondHeaviest))\n",
    "        return -heap[0] if heap else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) >= 2:\n",
    "            stones.sort()\n",
    "            y = stones.pop()\n",
    "            x = stones.pop()\n",
    "            if y > x:\n",
    "                stones.append(y - x)\n",
    "        if not stones:\n",
    "            return 0\n",
    "        else:\n",
    "            return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort(reverse=True)\n",
    "        print(stones)\n",
    "        length = len(stones)\n",
    "        while length>1:\n",
    "            if stones[0] == stones[1]:\n",
    "                length -= 2\n",
    "                if length == 0:\n",
    "                    return 0\n",
    "                stones = stones[2:]\n",
    "            else:\n",
    "                length -= 1\n",
    "                weight = stones[0]-stones[1]\n",
    "                if length == 1:\n",
    "                    return weight\n",
    "                stones = stones[2:]\n",
    "                if weight<stones[-1]:\n",
    "                    stones.append(weight)\n",
    "                else:\n",
    "                    for index in range(len(stones)):\n",
    "                        if stones[index]<=weight:\n",
    "                            stones.insert(index,weight)\n",
    "                            break\n",
    "            print(stones)\n",
    "            print(length)\n",
    "        return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        import heapq\n",
    "        max_heap = []\n",
    "        for stone in stones:\n",
    "            heapq.heappush(max_heap, -1*stone)\n",
    "        while len(max_heap) > 1:\n",
    "            x = -1*heapq.heappop(max_heap)\n",
    "            y = -1*heapq.heappop(max_heap)\n",
    "            if x != y:\n",
    "                heapq.heappush(max_heap, -1*abs(x-y))\n",
    "        if len(max_heap) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1*heapq.heappop(max_heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            l=sorted(stones,reverse = True)\n",
    "            y,x = l[0:2:]\n",
    "            if y==x:\n",
    "                stones.remove(x)\n",
    "                stones.remove(y)\n",
    "            else:\n",
    "                delta = y-x\n",
    "                stones.remove(x)\n",
    "                stones.remove(y)\n",
    "                stones.append(delta)\n",
    "        if stones==[]:\n",
    "            return 0\n",
    "        else:\n",
    "            return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort()\n",
    "        while len(stones) != 1:\n",
    "            y = stones.pop()\n",
    "            x = stones.pop()\n",
    "            if x == y:\n",
    "                pass\n",
    "            stones.insert(bisect.bisect_left(stones, y - x), y - x)\n",
    "        return stones[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 初始化\n",
    "        heap = [-stone for stone in stones]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        # 模拟\n",
    "        while len(heap) > 1:\n",
    "            x,y = heapq.heappop(heap),heapq.heappop(heap)\n",
    "            if x != y:\n",
    "                heapq.heappush(heap,x-y)\n",
    "\n",
    "        if heap: return -heap[0]\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            stones.sort(reverse=True)  # 从大到小排序\n",
    "            max1 = stones.pop(0)\n",
    "            max2 = stones.pop(0)\n",
    "            if max1 != max2:\n",
    "                stones.append(max1 - max2)\n",
    "        return stones[0] if stones else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort()\n",
    "        while len(stones) >= 2:\n",
    "            stones.sort()\n",
    "            if stones[-2] == stones[-1]:\n",
    "                stones = stones[:-2]\n",
    "            else:\n",
    "                stones = [abs(stones[-2] - stones[-1])] + stones[:-2]\n",
    "        return stones[0] if stones else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            stones.sort()\n",
    "            temp = stones[-1] - stones[-2]\n",
    "            stones = stones[:-2]\n",
    "            if temp != 0:\n",
    "                stones.append(temp)\n",
    "\n",
    "        if stones:\n",
    "            return stones[0]\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        new_stones = [-i for i in stones]\n",
    "        heapq.heapify(new_stones)\n",
    "        while len(new_stones) > 1:\n",
    "            x = heapq.heappop(new_stones)\n",
    "            y = heapq.heappop(new_stones)\n",
    "            if x != y:\n",
    "                heapq.heappush(new_stones, x - y)\n",
    "        if new_stones:\n",
    "            return -new_stones[0]\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    obj = Solution()\n",
    "    stones = [2, 7, 4, 1, 8, 1]\n",
    "    print(obj.lastStoneWeight(stones))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "#         stones = [-s for s in stones]\n",
    "#         heapq.heapify(stones)\n",
    "\n",
    "#         while len(stones) > 1:\n",
    "#             first = heapq.heappop(stones)\n",
    "#             second = heapq.heappop(stones)\n",
    "#             if second > first:\n",
    "#                 heapq.heappush(stones, first - second)\n",
    "\n",
    "#         stones.append(0)\n",
    "#         return abs(stones[0])\n",
    "\n",
    "# There's a private _heapify_max method.\n",
    "# https://github.com/python/cpython/blob/1170d5a292b46f754cd29c245a040f1602f70301/Lib/heapq.py#L198\n",
    "# class Solution(object):\n",
    "#     def lastStoneWeight(self, stones):\n",
    "#         heapq._heapify_max(stones)\n",
    "#         while len(stones) > 1:\n",
    "#             max_stone = heapq._heappop_max(stones)\n",
    "#             diff = max_stone - stones[0]\n",
    "#             if diff:\n",
    "#                 heapq._heapreplace_max(stones, diff)\n",
    "#             else:\n",
    "#                 heapq._heappop_max(stones)\n",
    "        \n",
    "#         stones.append(0)\n",
    "#         return stones[0]\n",
    "class MinHeap(object):\n",
    "\tdef __init__(self): self.h = []\n",
    "\tdef heappush(self, x): heapq.heappush(self.h, x)\n",
    "\tdef heappop(self): return heapq.heappop(self.h)\n",
    "\tdef __getitem__(self, i): return self.h[i]\n",
    "\tdef __len__(self): return len(self.h)\n",
    "    \n",
    "class MaxHeapObj(object):\n",
    "\tdef __init__(self, val): self.val = val\n",
    "\tdef __lt__(self, other): return self.val > other.val\n",
    "\tdef __eq__(self, other): return self.val == other.val\n",
    "\tdef __str__(self): return str(self.val)\n",
    "\n",
    "class MaxHeap(MinHeap):\n",
    "\tdef heappush(self, x): heapq.heappush(self.h, MaxHeapObj(x))\n",
    "\tdef heappop(self): return heapq.heappop(self.h).val\n",
    "\tdef __getitem__(self, i): return self.h[i].val\n",
    "\n",
    "class Solution(object):\n",
    "    def lastStoneWeight(self, stones):\n",
    "        maxHeap = MaxHeap()\n",
    "        for i in stones:\n",
    "            maxHeap.heappush(i)\n",
    "        while len(maxHeap) > 1:\n",
    "            first = maxHeap.heappop()\n",
    "            second = maxHeap.heappop()\n",
    "            if first > second:\n",
    "                maxHeap.heappush(first - second)\n",
    "        maxHeap.heappush(0)\n",
    "        return maxHeap.heappop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort(reverse=True)\n",
    "        n=len(stones)\n",
    "        while len(stones)>1:\n",
    "            stones[0]-=stones[1]\n",
    "            stones.pop(1)\n",
    "            stones.sort(reverse=True)\n",
    "        return stones[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:   \n",
    "        while stones:\n",
    "            if len(stones)==1:\n",
    "                return stones[0]\n",
    "            if len(stones)==0:\n",
    "                return 0\n",
    "            stones.sort(reverse=True)\n",
    "            x,y=stones[0],stones[1]\n",
    "            if x==y:\n",
    "                a=stones.pop(0)\n",
    "                b=stones.pop(0)\n",
    "            else:\n",
    "                stones[1]=x-y\n",
    "                a=stones.pop(0)\n",
    "        return stones[0] if stones else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) >= 2:\n",
    "            stones.sort()\n",
    "            y = stones.pop()\n",
    "            x = stones.pop()\n",
    "            if y > x:\n",
    "                stones.append(y - x)\n",
    "        if not stones:\n",
    "            return 0\n",
    "        else:\n",
    "            return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        max_stone = [-stone for stone in stones]\n",
    "        heapq.heapify(max_stone)\n",
    "\n",
    "        while len(max_stone) > 1:\n",
    "            stone1 = -heapq.heappop(max_stone)\n",
    "            stone2 = -heapq.heappop(max_stone)\n",
    "\n",
    "            if stone1 != stone2:\n",
    "                heapq.heappush(max_stone, -(stone1-stone2))\n",
    "\n",
    "        return -max_stone[0] if max_stone else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            x = max(stones)\n",
    "            stones.remove(x)\n",
    "            y = max(stones)\n",
    "            stones.remove(y)\n",
    "            if x != y:\n",
    "                stones.append(x-y)\n",
    "            \n",
    "        if len(stones) == 1:\n",
    "            return stones[0]\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort()\n",
    "        for i in range(len(stones)-1):\n",
    "            stones.sort()\n",
    "            res = stones[-1]- stones[-2]\n",
    "            if res == 0:\n",
    "                stones = stones[0:(len(stones)-2)]\n",
    "            else:\n",
    "                stones = stones[0:(len(stones)-2)]\n",
    "                stones.append(res)\n",
    "            if stones == []:\n",
    "                return 0\n",
    "            if len(stones) == 1:\n",
    "                break\n",
    "        return stones[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones = sorted(stones)\n",
    "\n",
    "        while len(stones)>1:\n",
    "            if stones[-1]==stones[-2]:\n",
    "                stones.pop()\n",
    "                stones.pop()\n",
    "\n",
    "            else:\n",
    "                stones[-2] = stones[-1]-stones[-2]\n",
    "                stones.pop()       \n",
    "                now = len(stones)-1\n",
    "                h = now -1\n",
    "                while h>=0:\n",
    "                    if stones[h]>=stones[now]:\n",
    "                        tmp = stones[h]\n",
    "                        stones[h] = stones[now]\n",
    "                        stones[now] = tmp\n",
    "                        now = h\n",
    "                        h = now-1\n",
    "                    else:\n",
    "                        break\n",
    "        \n",
    "        return stones[0] if stones!=[] else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        l1 = sorted(stones)\n",
    "        while len(l1) > 2:\n",
    "            if l1[-1] == l1[-2]:\n",
    "                l1.pop()\n",
    "                l1.pop()\n",
    "            else:\n",
    "                l1.append(l1[-1] - l1[-2])\n",
    "                l1.pop(-2)\n",
    "                l1.pop(-2)\n",
    "                l1 = sorted(l1)\n",
    "        if len(l1) == 2:\n",
    "            if l1[0] == l1[1]:\n",
    "                return 0\n",
    "            else:\n",
    "                return(l1[1] - l1[0])\n",
    "        else:\n",
    "            return (l1[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        max_heap = []\n",
    "        for stone in stones:\n",
    "            heapq.heappush(max_heap, -stone)\n",
    "        while len(max_heap) > 1:\n",
    "            first = heapq.heappop(max_heap)\n",
    "            second = heapq.heappop(max_heap)\n",
    "            if first == second:\n",
    "                continue\n",
    "            else:\n",
    "                heapq.heappush(max_heap, -second+first)\n",
    "        if len(max_heap) == 0:\n",
    "            return 0\n",
    "        return -max_heap[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\r\n",
    "        # 初始化\r\n",
    "        heap = [-stone for stone in stones]\r\n",
    "        heapq.heapify(heap)\r\n",
    "\r\n",
    "        # 模拟\r\n",
    "        while len(heap) > 1:\r\n",
    "            x,y = heapq.heappop(heap),heapq.heappop(heap)\r\n",
    "            if x != y:\r\n",
    "                heapq.heappush(heap,x-y)\r\n",
    "\r\n",
    "        if heap: return -heap[0]\r\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) >= 2:\n",
    "            stones.sort(reverse = True)\n",
    "            y = stones.pop(0)\n",
    "            x = stones.pop(0)\n",
    "            if y >x:\n",
    "                stones.append(y-x)\n",
    "        if not stones:\n",
    "            return 0\n",
    "        else:\n",
    "            return stones[0]\n",
    "    \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            stones.sort()\n",
    "            stones[-2] = stones[-1] - stones[-2]\n",
    "            stones.pop()\n",
    "        return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        n=len(stones)\n",
    "        if n==1:\n",
    "            return stones[0]\n",
    "        if n==2:\n",
    "            return abs(stones[1]-stones[0])\n",
    "        if n>2:\n",
    "            while n>1:\n",
    "                stones=sorted(stones)\n",
    "                n=len(stones)\n",
    "                a=stones[n-1]\n",
    "                b=stones[n-2]\n",
    "                stones.pop(n-1)\n",
    "                stones.pop(n-2)\n",
    "                stones.append(a-b)\n",
    "                n=len(stones)\n",
    "            return stones[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) >= 2:\n",
    "            stones.sort(reverse=True)\n",
    "            y = stones.pop(0)\n",
    "            x = stones.pop(0)\n",
    "            if y > x:\n",
    "                stones.append(y - x)\n",
    "        if not stones:\n",
    "            return 0\n",
    "        else:\n",
    "            return stones[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones =[-each for each in stones]\n",
    "        heapq.heapify(stones)\n",
    "        while len(stones) > 1:\n",
    "            val_1 = heapq.heappop(stones)\n",
    "            val_2 = heapq.heappop(stones)\n",
    "            result = -abs(val_1-val_2)\n",
    "            if result:\n",
    "                heapq.heappush(stones,result)\n",
    "        return -stones[0] if stones else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        n=len(stones)\n",
    "        if n==1:\n",
    "            return stones[0]\n",
    "        if n>1:\n",
    "            while n>1:\n",
    "                stones=sorted(stones)\n",
    "                n=len(stones)\n",
    "                a=stones[n-1]\n",
    "                b=stones[n-2]\n",
    "                stones.pop(n-1)\n",
    "                stones.pop(n-2)\n",
    "                stones.append(a-b)\n",
    "                n=len(stones)\n",
    "            return stones[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones)>0:\n",
    "            stones.sort()\n",
    "            if len(stones)==1:\n",
    "                return stones[0]\n",
    "            new = stones[-1]-stones[-2]\n",
    "            stones.pop()\n",
    "            stones.pop()\n",
    "            stones.append(new)\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        h_stone=[-x for x in stones]\n",
    "        heapify(h_stone)\n",
    "        while len(h_stone)>1:\n",
    "            a=heappop(h_stone)\n",
    "            b=heappop(h_stone)\n",
    "            if a!=b:\n",
    "                heappush(h_stone,-abs(a-b))\n",
    "        if len(h_stone)==1:\n",
    "            return -h_stone[0]\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        heap = [-stone for stone in stones]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        while len(heap) > 1:\n",
    "            x, y = heapq.heappop(heap), heapq.heappop(heap)\n",
    "            if x != y:\n",
    "                heapq.heappush(heap,x - y)\n",
    "        if heap: return -heap[0]\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            stones = sorted(stones)\n",
    "            x, y = stones[-2:]\n",
    "            if x == y:\n",
    "                stones.pop(-1)\n",
    "                stones.pop(-1)\n",
    "            else:\n",
    "                stones.pop(-1)\n",
    "                stones[-1] = y - x\n",
    "\n",
    "        return stones[0] if len(stones) > 0 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "堆的核心问题点\n",
    "一个中心\n",
    "① 动态求极值\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        # 初始化\n",
    "        # python heapq默认生成最小堆，可以通过取反，实现最大堆的目的\n",
    "        heap = [- stone for stone in stones]\n",
    "        # 列表堆化\n",
    "        heapq.heapify(heap)\n",
    "        # 遍历条件，剩余最后一个时间，直接返回\n",
    "        while len(heap) > 1:\n",
    "            # 从最大堆中取出最大值（两次）\n",
    "            x, y = heapq.heappop(heap), heapq.heappop(heap)\n",
    "            if x != y:\n",
    "                heapq.heappush(heap, x - y)\n",
    "        \n",
    "        if heap:\n",
    "            # 取反\n",
    "            return - heap[0]\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones)>1:\n",
    "            stones.sort()\n",
    "            a=stones[-1]\n",
    "            b=stones[-2]\n",
    "            stones.remove(a)\n",
    "            stones.remove(b)\n",
    "            stones.append(a-b)\n",
    "        if len(stones)==0:\n",
    "            return 0\n",
    "        else:\n",
    "            return stones[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        stones.sort()\n",
    "        if not stones:\n",
    "            return 0\n",
    "        elif len(stones)==1:\n",
    "            return stones[0]\n",
    "        elif len(stones) > 1:\n",
    "            x, y = stones.pop(), stones.pop()\n",
    "\n",
    "\n",
    "        if x != y:\n",
    "            stones.append(max(x, y) - min(x, y))\n",
    "        if not stones:\n",
    "            return 0\n",
    "        elif len(stones) == 1:\n",
    "            return stones[0]\n",
    "        else:\n",
    "            return self.lastStoneWeight(stones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\r\n",
    "        for i in range(len(stones)): stones[i]=-stones[i]\r\n",
    "        heapify(stones)\r\n",
    "        while len(stones)>1:\r\n",
    "            x,y=heappop(stones),heappop(stones)\r\n",
    "            if x!=y: heappush(stones,-abs(y-x))\r\n",
    "        return 0 if len(stones)==0 else -stones[0]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeight(self, stones: List[int]) -> int:\n",
    "        while len(stones) > 1:\n",
    "            stones.sort(reverse=True)  # 从大到小排序\n",
    "            max1 = stones.pop(0)\n",
    "            max2 = stones.pop(0)\n",
    "            if max1 != max2:\n",
    "                stones.append(max1 - max2)\n",
    "        return stones[0] if len(stones) == 1 else 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
